Structured ASICs may be used to implement large systems that include millions of gates and megabits of embedded memory. Of the tasks required in managing and optimizing a design, designing components and placement of the components on the structured ASICs utilizing available resources can be the most challenging and time consuming. In order to satisfy placement and timing specifications, EDA tools are used to manage and optimize their design onto physical target devices. Automated synthesis and placement algorithms in EDA tools perform the time consuming task of designing and placement of components onto physical devices.
As the complexity of circuits increase, traditional synthesis methods often are unable to produce a timing optimal solution. Delays associated with unplaced circuits are difficult to estimate which make optimization for timing challenging for the traditional synthesis methods. One approach taken by circuit designers to improve timing is to perform physical synthesis which involves re-synthesizing the circuit incrementally after placement. Physical synthesis allows delays to be modeled more accurately after placement when cell positions have been determined.
The optimizations that are performed during physical synthesis will usually lead to a placement that is illegal. For example, one optimization technique that is commonly used is component duplication where nodes feeding a critical connection are duplicated and the duplicated node is moved to its critical fanout connection. A problem with this optimization technique is that congestion often occurs after duplication. When modifications made to a system produce a placement that is illegal, current EDA tools require a re-work of the entire placement procedure. This may require a significant amount of time which is inefficient and undesirable.
Thus, what is needed is an efficient method and apparatus for performing incremental placement on a structured ASIC.